<HTML>
<!--
  -- Copyright (c) 1996-1999
  -- Silicon Graphics Computer Systems, Inc.
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Silicon Graphics makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -- Copyright (c) 1994
  -- Hewlett-Packard Company
  --
  -- Permission to use, copy, modify, distribute and sell this software
  -- and its documentation for any purpose is hereby granted without fee,
  -- provided that the above copyright notice appears in all copies and
  -- that both that copyright notice and this permission notice appear
  -- in supporting documentation.  Hewlett-Packard Company makes no
  -- representations about the suitability of this software for any
  -- purpose.  It is provided "as is" without express or implied warranty.
  --
  -->
<Head>
<Title>equal_range</Title>
<!-- Generated by htmldoc -->
</HEAD>
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 
	ALINK="#ff0000"> 
<IMG SRC="CorpID.gif" 
     ALT="SGI" HEIGHT="43" WIDTH="151"> 
<!--end header-->
<BR Clear>
<H1>equal_range</H1>

<Table CellPadding=0 CellSpacing=0 width=100%>
<TR>
<TD Align=left><Img src = "algorithms.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
<TD Align=right><Img src = "function.gif" Alt=""   WIDTH = "194"  HEIGHT = "38" ></TD>
</TR>
<TR>
<TD Align=left VAlign=top><b>Category</b>: algorithms</TD>
<TD Align=right VAlign=top><b>Component type</b>: function</TD>
</TR>
</Table>

<h3>Prototype</h3>
<tt>Equal_range</tt> is an overloaded name; there are actually two <tt>equal_range</tt>
functions.
<pre>
template &lt;class <A href="ForwardIterator.html">ForwardIterator</A>, class <A href="LessThanComparable.html">LessThanComparable</A>&gt;
<A href="pair.html">pair</A>&lt;ForwardIterator, ForwardIterator&gt;
equal_range(ForwardIterator first, ForwardIterator last,
            const LessThanComparable&amp; value);

template &lt;class <A href="ForwardIterator.html">ForwardIterator</A>, class T, class <A href="StrictWeakOrdering.html">StrictWeakOrdering</A>&gt;
<A href="pair.html">pair</A>&lt;ForwardIterator, ForwardIterator&gt;
equal_range(ForwardIterator first, ForwardIterator last, const T&amp; value,
            StrictWeakOrdering comp);

</pre>                   
<h3>Description</h3>
<tt>Equal_range</tt> is a version of binary search: it attempts to find the
element <tt>value</tt> in an ordered range <tt>[first, last)</tt> <A href="#1">[1]</A>.  The
value returned by <tt>equal_range</tt> is essentially a combination of
the values returned by <tt><A href="lower_bound.html">lower_bound</A></tt> and <tt><A href="upper_bound.html">upper_bound</A></tt>:
it returns a pair of iterators <tt>i</tt> and <tt>j</tt> such that <tt>i</tt> is the 
first position where <tt>value</tt> could be inserted without violating
the ordering and <tt>j</tt> is the last position where <tt>value</tt> could be
inserted without violating the ordering.  It follows that every
element in the range <tt>[i, j)</tt> is equivalent to <A href="#1">[1]</A> <tt>value</tt>, and that
<tt>[i, j)</tt> is the largest subrange of <tt>[first, last)</tt> that has this
property.  The first version of <tt>equal_range</tt>
uses <tt>operator&lt;</tt> for comparison, and the second uses the 
<A href="functors.html">function object</A> <tt>comp</tt>.
<P>
The first version of <tt>equal_range</tt> returns a pair of iterators <tt>[i, j)</tt>.
<tt>i</tt> is the furthermost iterator in <tt>[first, last)</tt> such that, for
every iterator <tt>k</tt> in <tt>[first, i)</tt>, <tt>*k &lt; value</tt>.  <tt>j</tt> is the
furthermost iterator in <tt>[first, last)</tt> such that, for every iterator
<tt>k</tt> in <tt>[first, j)</tt>, <tt>value &lt; *k</tt> is <tt>false</tt>.  For every iterator 
<tt>k</tt> in <tt>[i, j)</tt>, neither <tt>value &lt; *k</tt> nor <tt>*k &lt; value</tt> is <tt>true</tt>. <A href="#2">[2]</A>
<P>
The second version of <tt>equal_range</tt> returns a pair of iterators <tt>[i,
j)</tt>.  <tt>i</tt> is the furthermost iterator in <tt>[first, last)</tt> such that,
for every iterator <tt>k</tt> in <tt>[first, i)</tt>, <tt>comp(*k, value)</tt> is <tt>true</tt>.
<tt>j</tt> is the furthermost iterator in <tt>[first, last)</tt> such that, for
every iterator <tt>k</tt> in <tt>[first, j)</tt>, <tt>comp(value, *k)</tt> is <tt>false</tt>.  For
every iterator <tt>k</tt> in <tt>[i, j)</tt>, neither <tt>comp(value, *k)</tt> nor
<tt>comp(*k, value)</tt> is <tt>true</tt>. <A href="#2">[2]</A>
<h3>Definition</h3>
Defined in the standard header <A href="algorithm">algorithm</A>, and in the nonstandard
backward-compatibility header <A href="algo.h">algo.h</A>.
<h3>Requirements on types</h3>
For the first version:
<UL>
<LI>
<tt>ForwardIterator</tt> is a model of <A href="ForwardIterator.html">Forward Iterator</A>.
<LI>
<tt>LessThanComparable</tt> is a model of <A href="LessThanComparable.html">LessThan Comparable</A>.
<LI>
The ordering on objects of type <tt>LessThanComparable</tt> is a <i>strict
   weak ordering</i>, as defined in the <A href="LessThanComparable.html">LessThan Comparable</A> requirements.
<LI>
<tt>ForwardIterator</tt>'s value type is the same type as <tt>LessThanComparable</tt>.
</UL>
For the second version:
<UL>
<LI>
<tt>ForwardIterator</tt> is a model of <A href="ForwardIterator.html">Forward Iterator</A>.
<LI>
<tt>StrictWeakOrdering</tt> is a model of <A href="StrictWeakOrdering.html">Strict Weak Ordering</A>.
<LI>
<tt>ForwardIterator</tt>'s value type is the same type as <tt>T</tt>.
<LI>
<tt>ForwardIterator</tt>'s value type is convertible to <tt>StrictWeakOrdering</tt>'s
   argument type.
</UL>
<h3>Preconditions</h3>
For the first version:
<UL>
<LI>
<tt>[first, last)</tt> is a valid range.
<LI>
<tt>[first, last)</tt> is ordered in ascending order according to
   <tt>operator&lt;</tt>.  That is, for every pair of iterators <tt>i</tt> and <tt>j</tt>
   in <tt>[first, last)</tt> such that <tt>i</tt> precedes <tt>j</tt>, 
   <tt>*j &lt; *i</tt> is <tt>false</tt>.
</UL>
For the second version:
<UL>
<LI>
<tt>[first, last)</tt> is a valid range.
<LI>
<tt>[first, last)</tt> is ordered in ascending order according to
   the <A href="functors.html">function object</A> <tt>comp</tt>.  That is, for every pair of iterators <tt>i</tt> and <tt>j</tt>
   in <tt>[first, last)</tt> such that <tt>i</tt> precedes <tt>j</tt>, 
   <tt>comp(*j, *i)</tt> is <tt>false</tt>.
</UL>
<h3>Complexity</h3>
The number of comparisons is logarithmic: at most <tt>2 * log(last - first) +
1</tt>.  If <tt>ForwardIterator</tt> is a <A href="RandomAccessIterator.html">Random Access Iterator</A> then the
number of steps through the range is also logarithmic; otherwise, 
the number of steps is proportional to <tt>last - first</tt>.  <A href="#3">[3]</A>
<h3>Example</h3>
<pre>
int main()
{
  int A[] = { 1, 2, 3, 3, 3, 5, 8 };
  const int N = sizeof(A) / sizeof(int);

  for (int i = 2; i &lt;= 4; ++i) {
    pair&lt;int*, int*&gt; result = equal_range(A, A + N, i);

    cout &lt;&lt; endl;
    cout &lt;&lt; &quot;Searching for &quot; &lt;&lt; i &lt;&lt; endl;
    cout &lt;&lt; &quot;  First position where &quot; &lt;&lt; i &lt;&lt; &quot; could be inserted: &quot;
         &lt;&lt; result.first - A &lt;&lt; endl;
    cout &lt;&lt; &quot;  Last position where &quot; &lt;&lt; i &lt;&lt; &quot; could be inserted: &quot;
         &lt;&lt; result.second - A &lt;&lt; endl;
    if (result.first &lt; A + N)
      cout &lt;&lt; &quot;  *result.first = &quot; &lt;&lt; *result.first &lt;&lt; endl;
    if (result.second &lt; A + N)
      cout &lt;&lt; &quot;  *result.second = &quot; &lt;&lt; *result.second &lt;&lt; endl;
  }
}    
</pre>
The output is:
<pre>
Searching for 2
  First position where 2 could be inserted: 1
  Last position where 2 could be inserted: 2
  *result.first = 2
  *result.second = 3

Searching for 3
  First position where 3 could be inserted: 2
  Last position where 3 could be inserted: 5
  *result.first = 3
  *result.second = 5

Searching for 4
  First position where 4 could be inserted: 5
  Last position where 4 could be inserted: 5
  *result.first = 5
  *result.second = 5
</pre>
<h3>Notes</h3>
<P><A name="1">[1]</A>
Note that you may use an ordering that is a strict weak ordering
but not a total ordering; that is, there might be values <tt>x</tt> and <tt>y</tt>
such that <tt>x &lt; y</tt>, <tt>x &gt; y</tt>, and <tt>x == y</tt> are all <tt>false</tt>.  (See the
<A href="LessThanComparable.html">LessThan Comparable</A> requirements for a more complete discussion.)
Finding <tt>value</tt> in the range <tt>[first, last)</tt>, then, doesn't mean
finding an element that is equal to <tt>value</tt> but rather one that is
<i>equivalent to</i> <tt>value</tt>: one that is neither greater than nor less
than <tt>value</tt>.  If you're using a total ordering, however (if you're
using <tt>strcmp</tt>, for example, or if you're using ordinary arithmetic
comparison on integers), then you can ignore this technical
distinction: for a total ordering, equality and equivalence are
the same.
<P><A name="2">[2]</A>
Note that <tt>equal_range</tt> may return an empty range; that is, it
may return a pair both of whose elements are the same iterator.
<tt>Equal_range</tt> returns an empty range if and only if the range <tt>[first,
last)</tt> contains no elements equivalent to <tt>value</tt>.  In this case it
follows that there is only one position where <tt>value</tt> could be
inserted without violating the range's ordering, so the return value
is a pair both of whose elements are iterators that point to that
position.
<P><A name="3">[3]</A>
This difference between <A href="RandomAccessIterator.html">Random Access Iterators</A> and
<A href="ForwardIterator.html">Forward Iterators</A> is simply because <tt><A href="advance.html">advance</A></tt> is constant
time for <A href="RandomAccessIterator.html">Random Access Iterators</A> and linear time for 
<A href="ForwardIterator.html">Forward Iterators</A>.
<h3>See also</h3>
<tt><A href="lower_bound.html">lower_bound</A></tt>, <tt><A href="upper_bound.html">upper_bound</A></tt>, <tt><A href="binary_search.html">binary_search</A></tt>

<!--start footer--> 
<HR SIZE="6">
<A href="http://www.sgi.com/"><IMG SRC="surf.gif" HEIGHT="54" WIDTH="54" 
        ALT="[Silicon Surf]"></A>
<A HREF="index.html"><IMG SRC="stl_home.gif" 
        HEIGHT="54" WIDTH="54" ALT="[STL Home]"></A>
<BR>
<FONT SIZE="-2">
<A href="http://www.sgi.com/Misc/sgi_info.html" TARGET="_top">Copyright &copy; 
1999 Silicon Graphics, Inc.</A> All Rights Reserved.</FONT>
<FONT SIZE="-3"><a href="http://www.sgi.com/Misc/external.list.html" TARGET="_top">TrademarkInformation</A>
</FONT>
<P>
</BODY>
</HTML> 
